One-time authentication tokens produce unpredictable one-time passcodes (OTP) typically by extracting pseudorandomness from a secret seed, that is stored at the token and shared with the authentication server. To protect against server-side leakage of the underlying seed, tokens may employ split-server verification protocols (see, e.g., U.S. Pat. No. 7,725,730). In a split-server verification protocol, the underlying authentication secret is split into at least two partial secrets, each one kept by a distinct verification server, so that authentication of a user is performed at these servers in a distributed manner so that certain attacks against one or more servers can be tolerated.
A number of such split-server OTP verification protocols have been proposed. See, for example, U.S. patent application Ser. No. 13/404,737, entitled “Method and Apparatus for Authenticating a User Using Multi-Server One-Time Passcode Verification,” (now U.S. Pat. No. 9,118,661); U.S. patent application Ser. No. 13/795,801, entitled “Distributed Cryptography Using Distinct Value Sets Each Comprising At Least One Obscured Secret Value;” (now U.S. Pat. No. 9,037,858); and U.S. patent application Ser. No. 14/144,707, entitled “Multi-Server One-Time Passcode Verification of Respective High Order and Low Order Passcode Portions,” (now U.S. Pat. No. 9,454,654).
While such split-server solutions have successfully addressed the security problems related to possible server-side compromises and secret leakage, at the same time they introduce a new issue due to possible benign failures or unavailability of one or more of the verification servers. For example, in a two-server architecture, if one of the two servers becomes unavailable, e.g., due to internal software or hardware failures or due to networking problems, then the system immediately becomes unable to handle incoming split-server authentication attempts by users. The correct passcode cannot be reconstructed as one of the passcode components is not retrievable.
Replication-based server-recovery solutions can be employed to mitigate this problem in the split-server setting, but they tend to be costly, as they increase operational and maintenance costs as well as the storage needs of the entire system. In addition, such replication-based server-recovery solutions also replicate the secret states of the system, thus negatively affecting the security of the system since they offer a wider attack vector to the adversary. An attacker now has more options as to which servers to select for an attack. Indeed, the attacker may choose to attack a replica server that can potentially be an easier target.
Thus, a need exists for efficient recovery schemes for split-server OTP verification systems that do not rely on replication (if needed, such schemes can be actually complementary to standard replication-based solutions). A further need exists for a recovery mechanism for split-server OTP verification systems that allows the system to operate smoothly and unaffectedly even in the event of a server going temporarily or permanently down.